#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef struct postion
{
	int row;
	int clo;
}PT;
typedef PT type;
typedef struct stack
{
	type* a;
	int capacity;
	int top;
}ST;
void StackInit(ST* s)
{
	s->top = 0;
	s->capacity = 0;
	s->a = NULL;
}

void StackPush(ST* s, type x)
{
	assert(s);
	if (s->capacity == s->top)
	{
		//
		int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
		type* temp = (type*)realloc(s->a, sizeof(type) * newcapacity);
		s->a = temp;
		s->capacity = newcapacity;
	}
	//Ԫ
	s->a[s->top] = x;
	s->top++;
}

bool StackEmpty(ST* s)
{
	assert(s);
	return s->top == 0;
}

void StackDestory(ST* s)
{
	assert(s);
	s->top = 0;
	s->a = NULL;
	s->capacity = 0;
}

type StackTop(ST* s)
{
	assert(s);
	assert(!StackEmpty(s));
	return s->a[s->top - 1];
}

void StackPop(ST* s)
{
	assert(s);
	assert(!StackEmpty(s));
	s->top--;
}
ST path;
void Display(int** maze, int N, int M)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
}

void PrintPath(ST* ps)
{
	ST rPath;
	StackInit(&rPath);
	while (!StackEmpty(&path))
	{
		StackPush(&rPath, StackTop(&path));
		StackPop(&path);
	}
	while (!StackEmpty(&rPath))
	{
		PT top = StackTop(&rPath);
		printf("(%d,%d)\n", top.row, top.clo);
		StackPop(&rPath);
	}
	StackDestory(&rPath);
}
bool Ispass(int** maze, int N, int M, PT pos)
{
	if (pos.row >= 0
		&& pos.row < N
		&& pos.clo >= 0
		&& pos.clo < M
		&& maze[pos.row][pos.clo] == 0)
	{
		return true;
	}
	else
	{
		return false;

	}

}
//传迷宫的指针，是为了修改迷宫的数据，传N,M是为了判断是否越界，迷宫的横纵坐标用了一个结构体封装
//cur于next的使用达到了next走起来的效果
bool GetMazePath(int** maze, int N, int M, PT cur)
{
	//不管三七二十一向将位置坐标入栈，当碰壁的时候，再将栈顶元素弹栈
	StackPush(&path, cur);
	//递归结束的条件：也就是达到出口
	if (cur.row == N - 1 && cur.clo == M - 1)
	{
		return true;
	}
	PT next;
	//遍历过就将迷宫数组改点的值改为2，防止再次遍历
	maze[cur.row][cur.clo] = 2;
	next = cur;
	//判断上
	next.row -= 1;
	// ispass函数的实现就是 看他是否越界和是否被访问过，没有就返回ture，否则flase
	if (Ispass(maze, N, M, next))
	{
		if (GetMazePath(maze, N, M, next))
		{
			return true;
		}
	}

	next = cur;
	next.row += 1;
	//判读下
	if (Ispass(maze, N, M, next))
	{
		if (GetMazePath(maze, N, M, next))
		{
			return true;
		}
	}

	next = cur;
	next.clo -= 1;
	//判断左
	if (Ispass(maze, N, M, next))
	{
		if (GetMazePath(maze, N, M, next))
		{
			return true;
		}
	}

	next = cur;
	next.clo += 1;
	//判断右
	if (Ispass(maze, N, M, next))
	{
		if (GetMazePath(maze, N, M, next))
		{
			return true;
		}
	}
	StackPop(&path);
	return false;

}

int main()
{
	int N = 0, M = 0;
	printf("===迷宫===\n");
	while (scanf("%d %d", &N, &M) != EOF)//输入迷宫的长和宽
	{
		//用二级指针创建二维数组的迷宫
		int** maze = (int**)malloc(sizeof(int*) * N);
		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int) * M);
		}
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}
		//Display(maze,N,M);
		StackInit(&path);
		PT entry = { 0,0 };
		//探测迷宫的上下左右，如果不是通路就依赖于递归的性质返回到上一个位置，
		//这样遍历迷宫类似于二叉树的深度遍历（前中后序等）
		if (GetMazePath(maze, N, M, entry))
		{
			printf("迷宫通路为\n");
			PrintPath(&path);
		}
		else 
		{
			printf("没有这样的通路\n");

		}
		StackDestory(&path);
		//由于迷宫是malloc出来的所以不要忘了释放
		for (int i = 0; i < N; i++)
		{
			free(maze[i]);
		}
		free(maze);
		maze = NULL;
	}
	return 0;
}